将数组拆分成斐波那契序列(Leetcode 842)

题目分析

   题目看起来非常简单，操作起来比较复杂，尤其是使用C++语言进行解答时，比Python语言困难得多。

迭代

先给小伙伴们介绍一下迭代解法，思路非常简答，枚举前两个数，然后递推后面的数即可。

其中介绍代码中一些变量的意义，其中p0等于0，说明第一个数是从0号索引开始的，p1从1到(S.size() + 1) / 2，当p1 = k时，说明第一个数的长度为k，因为第三个数的长度一定大于等于第一个，因此第一个数最多只有字符串长度的一半。p2是第三个数是从p2开始的。所以f0 = S.substr(0, p1)，f1 = S.substr(p1, p2 - p1)。

然后我们令curF0 = f0，curF1 = f1，curF2 = f0 + f1，curP2 = p2，我们只要查看S字符串从curP2开始，是否出现curF2即可。如果没有出现，说明f0和f1构造的不正确，如果出现则继续判断下一个元素是否出现。

因为我们只要枚举前两个数，每一次最多枚举log(C)位，在每一次枚举中，都需要验证后面的斐波那契数列是否正确，因此算法的**时间复杂度为$O(nlog^2(C))$，空间复杂度为$O(1)$**，其中C是整数的范围。

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        vector<int> res;
        char tmpC[20];
        sprintf(tmpC, "%d", INT32_MAX);
        string maxi = tmpC;
        for (int p1 = 1; p1 < (S.size() + 1) / 2; p1++) {
            string s0 = S.substr(0, p1);
            if ((s0.size() > 1 && s0.substr(0, 1) == "0") || (s0.size() > maxi.size() || (s0.size() == maxi.size() && s0 > maxi))) { break; }
            long long f0 = stoll(s0);
            for (int p2 = p1 + 1; p2 < S.size(); p2++) {
                string s1 = S.substr(p1, p2 - p1);
                if ((s1.size() > 1 && s1.substr(0, 1) == "0") || (s1.size() > maxi.size() || (s1.size() == maxi.size() && s1 > maxi))) { break; }
                long long f1 = stoll(s1);
                long long curF0 = f0, curF1 = f1, curF2 = f0 + f1;
                int curP2 = p2;
                res.push_back(int(curF0));
                res.push_back(int(curF1));
                bool flag = true;
                while (curP2 < S.size() && flag) {
                    sprintf(tmpC, "%d", curF2);
                    string tmp = tmpC;
                    if (curF2 > INT32_MAX || (tmp.size() > 1 && tmp.substr(0, 1) == "0") || tmp.size() + curP2 > S.size() || tmpC != S.substr(curP2, tmp.size())) { flag = false; }
                    else {
                        res.push_back(int(curF2));
                        long long curF3 = curF1 + curF2;
                        curF0 = curF1, curF1 = curF2, curF2 = curF3;
                        curP2 += tmp.size();
                    }
                }
                if (flag) { return res; }
                else { res.clear(); }
            }
        }
        return res;
    }
};

递归/DFS

DFS也是一种递归，我们已知前两个数，和前一个数，去搜索当前数值。这就是一种深度优先搜索算法。只不过稍微复杂的是在搜索过程中要判断，当数组中没有前两个数时，我们要将当前的结果不加判断的加入到数组中去搜索。只有数组中存在了两个数据时，我们才能验证第三个数是否正确。

因为我们只需要搜索一个数据，因此我们一旦搜到字符串结尾，说明找到了一个合理的路径，因此return true即可。

算法的**时间复杂度为$O(nlog^2(C))$，空间复杂度为$O(n)$**，其中C是整数的范围，空间复杂度变大是因为函数会调用栈空间，最多为n层。

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        vector<int> res;
        dfs(S, res, 0, S.size(), 0, 0);
        return res;
    }

    bool dfs(string S, vector<int>& res, int idx, int length, int sum, int f1) {
        if (idx == length) {
            return res.size() >= 3;
        }
        long long f2 = 0;
        for (int i = idx; i < length; i++) {
            if (i > idx && S[idx] == '0') { break; }
            f2 = f2 * 10 + (S[i] - '0');
            if (f2 > INT32_MAX) { break; }
            if (res.size() >= 2) {
                if (f2 < sum) { continue; }
                else if (f2 > sum) { break; }
            }
            res.push_back(f2);
            if (dfs(S, res, i + 1, length, f1 + f2, f2)) {
                return true;
            }
            res.pop_back();
        }
        return false;
    }
};

BFS

能用DFS的题目，我一般都会使用BFS再做一次，只不过是将DFS中的参数列表封装起来，然后使用deque双端队列来手动实现BFS。其代码核心部分基本上是不变的。

如果只想求一条路径，那么在第一次搜索到的时候直接return即可，那么它一定是最短的那一条。BFS搜索一条和搜索全部的时间复杂都是相同的，因为BFS搜索会将所有的斐波那契数列都保存下来，因此我就将本题做了扩展，求出所有的斐波那契数列，返回任意一条即可。

代码的核心内容和DFS完全一样，只不过要将DFS的参数用一个类封装起来。

但是时间复杂度要大得多，因为这个题目的特殊性，以及要求除0外首位不能为0，时间复杂度会大大缩小，因此这个算法是可以通过的。

#include<iostream>
#include<vector>
#include<deque>
#include<string>

using namespace std;

class Element {
public:
    vector<int> array;
    int idx, sum, f1;

    Element(vector<int>& array, int idx, int sum, int f1) {
        this->array = array;
        this->idx = idx;
        this->sum = sum;
        this->f1 = f1;
    }
};

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        int length = S.size();
        vector<vector<int>> res;
        vector<int> v = {};
        deque<Element*> queue = { new Element(v, 0, 0, 0) };
        while (!queue.empty()) {
            Element* cur = queue.front();
            queue.pop_front();
            if (cur->idx == length && cur->array.size() >= 3) {
                res.push_back(cur->array);
                continue;
            }
            long f2 = 0;
            for (int i = cur->idx; i < length; i++) {
                if (i > cur->idx && S[cur->idx] == '0') { break; }
                f2 = 10 * f2 + (S[i] - '0');
                if (f2 > INT32_MAX) { break; }
                if (cur->array.size() >= 2) {
                    if (f2 > cur->sum) { break; }
                    else if (f2 < cur->sum) { continue; }
                }
                cur->array.push_back(f2);
                queue.push_back(new Element(cur->array, i + 1, cur->f1 + f2, f2));
                cur->array.pop_back();
            }
        }
        return res.size() ? res[0] : vector<int>();
    }
};

刷题总结

  搜索类的题目是笔试面试的常考题型，已经多次强调，要想拿到心动的offer，那就赶紧刷题吧。